package com.example.bst;

/**
 * @Date 2022/4/6
 * @Created by Jonathan
 */
public class MaxDistanceBST {
    static class Node {
        Integer value;
        Node right;
        Node left;
    }

    static class Info {
        Integer height; // 当前节点的高度
        Integer maxDistance; // 以当前节点为头节点的二叉树的最大距离

        public Info(Integer height, Integer maxDistance) {
            this.height = height;
            this.maxDistance = maxDistance;
        }
    }

    private Info process(Node node) {
        // base case
        if (node == null)
            return new Info(0, 0);
        // 处理左边
        Info left = process(node.left);
        // 处理右边
        Info right = process(node.right);
        //  若经过当前节点 就是左边的高度+右边的高度+1
        // 若不经过当前节点 就是左边或者右边的最大距离
        // 再将上面两个比较大小
        Integer maxDistance = Math.max(left.height + right.height + 1, Math.max(left.maxDistance, right.maxDistance));
        Integer height = Math.max(left.height, right.height) + 1;
        return new Info(height, maxDistance);
    }

    public Integer getMaxDistance(Node head) {
        return process(head).maxDistance;
    }
}
